package tree;

/**
 * 并查集练习
 * 并查集是一种特殊的树结构，由孩子节点指向父节点
 * 时间复杂度：O(h),h为树的高度
 *
 */
public class MyUnionFind implements UF{

    private int[] parent;   // parent[i] 为 i 元素的父节点
    private int[] rank;     // rank[i] ：以元素i为根节点的树的高度


    public MyUnionFind(int size){
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;//让所有元素的父节点指向自己

            rank[i] = 1; //初始化以i为根节点的树的高度
        }

    }


    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }


    /**
     * 元素合并
     * 路径压缩：将rank低的合并到rank高的节点上
     * @param p
     * @param q
     */
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);    //p的root节点
        int qRoot = find(q);    //q的root节点

        //元素的根节点为同一个，那就不需要合并
        if(pRoot == qRoot){
            return;
        }

        if(rank[pRoot] < rank[qRoot]){  //第一种情况：pRoot所在的树的高度 小于 qRoot所在树的高度
            //将pRoot的根节点指向qRoot的根节点
            parent[pRoot] = qRoot;
            //因为rank其实并没有变化，所有不需要
        }else if (rank[pRoot] > rank[qRoot]){   // 第二种情况：pRoot所在的树的高度 大于 qRoot所在树的高度
            rank[qRoot] = pRoot;
            //因为rank其实并没有变化，所有不需要
        }else {
            // 第三种情况：两个元素的rank相等，那么合并之后，需要让rank+1
            rank[qRoot] = pRoot;
            rank[pRoot] = rank[pRoot] + 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    /**
     * 查找元素p元素所对应的父节点
     * 路径压缩（ Path Compression ）：将p父节点，指向p父节点的父节点 parent[p] = parent[parent[p]];
     * @param p
     * @return
     *
     */
    private int find(int p){

        while (p != parent[p]){ //p = parent[p] 表示已经遍历到根节点了
            //路径压缩，让p指向p的父节点的父节点，使路径长度-1
            parent[p] = parent[parent[p]];
            //遍历增量
            p = parent[p];
        }
        return p;
    }


}
